public class Node {
public long value;
public Node next;
public Node(long value) {
    this.value = value;
    this.next = null;
}
public static Node sortedInsert(Node head, Node newNode) {
    if (head == null || head.value >= newNode.value) {
        newNode.next = head;    // 将新节点的next指向当前的头节点
        head = newNode;     // 更新头节点为新节点
    } else {
        Node current = head;
        // 遍历已排序链表，直到找到第一个值大于新节点的节点
        while (current.next != null && current.next.value < newNode.value) {
            current = current.next;
        }
        newNode.next = current.next;    // 插入新节点到找到的位置
        current.next = newNode;
    }
    return head;     // 返回已排序链表的头节点
}
public static Node insertionSort(Node head) {
    if (head == null || head.next == null) {
        return head;       // 如果链表为空或者只有一个节点，直接返回
    }
    Node sorted = null;      // 当前节点从原始链表头开始
    Node current = head;
    while (current != null) {
        Node next = current.next;  // 保存当前节点的下一个节点
        sorted = sortedInsert(sorted, current); // 将当前节点插入到已排序链表的正确位置
        current = next; // 移动到原始链表的下一个节点
    }
    return sorted;
}

// 打印链表
public static void printList(Node head) {
    System.out.print("[");
    while (head != null) {
        System.out.print(head.value);
        if (head.next != null) {
            System.out.print(", ");
        }
        head = head.next;
    }
    System.out.println("]");
}
public static void main(String[] args) {
    Node node = new Node(111);
    Node node1 = new Node(333);
    Node node2 = new Node(9999);
    Node node3 = new Node(66);
    Node node4 = new Node(112);
    Node node5 = new Node(213);
    Node node6 = new Node(447);
    Node node7 = new Node(168);
    Node node8 = new Node(1);
    Node node9 = new Node(4321);
    Node node10 = new Node(8787);
    Node node11 = new Node(20240311018L);
    node.next = node1;
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node6;
    node6.next = node7;
    node7.next = node8;
    node8.next = node9;
    node9.next = node10;
    node10.next = node11;
    node = insertionSort(node);
    System.out.println("进行升序排序后的链表：");
    printList(node);
    }
}
